CS 206							 
HANDOUT #20
05-02-74

                 	   POSSIBLE PROJECTS

	Projects come in two flavors: additions and corrections to
existing programs, and "new starts."  In addition to a source listing
and test output, you will be expected to provide a description of what
your program/addition/correction does, your method and your reasons
for choosing that method.

1. MILISY.  A natural language program.
	MILISY (see HANDOUT #17) is an existing natural language program
written in LISP. It accepts simple English language assertions about
its "world" (e.g., A RED BLOCK IS ON A TABLE) and answers questions
(e.g., WHICH BLOCK IS ON THE TABLE).  A suitable project would be to
add relative clauses and one other worthwhile addition or correction.
See the other handout for details.

2. SPOT.  A program which learns structural descriptions by example.
	SPOT is a learning program, written in LISP, which is similar	
in concept, though not in sophistication, to P. H. Winston's learning
program.  The program accepts a named "scene" which is an example of
a particular structural type (e.g., ARCH (A B C) (A SUPPORTS C)
(B SUPPORTS C) (A BLOCK) (B BLOCK) (C PYRAMID), which is an example
of an arch). SPOT may learn more about the "scene" through further
examples.  After sufficient information has been gathered, it is
capable of identifying an unnamed scene as an example of some 
structure about which it knows.  Making SPOT "remember" structures
(so that, for example, a VIADUCT could be recognized as several
ARCHes) and implementing repeated structures (e.g., a BRICK WALL)
would constitute a suitable project.  Further information on this
project will be available shortly.

3. Program optimization.
	This is a new project.  In "A System Which Automatically Improves
Programs" (3rd IJCAI, pp 479-485.  on reserve for AI qual), Darlington
and Burstall describe a system which optimizes a source program.
They present methods for recursion removal, "factoring" of common
subexpressions, merging of loops, a (particularly interesting)
method of optimizing adjacent calls to the same function, etc.  
A suitable project entails implementing recursion removal, "factoring"
of common subexpressions and either "compound operations" (optimizing
adjacent function calls) or merging of loops.

4. MINIT.  A mini theorem prover for the propositional calculus.
	Although this is an existing program (written in MLISP), it
is a "high-risk" project.  MINIT runs - sort of.  Previous projects
have attempted to extend it to predicate calculus, and it has a number
of interesting (and subtle) bugs which should be corrected.  A
suitable project would be to make MINIT run correctly and/or implement
some of the strategies described in the last chapter of Nilsson.
Again, further information will be available in a short time.

5. Polya enumeration.
	This project involves modifications to an existing INTERLISP
program. (Incompatibilities may force a complete rewrite into UCI LISP.)
The general problem is to compute the number of different colorings of a
set of N objects under symmetry group G contained in Sn, coloring n1 of 
the objects with color 1, n2 with color 2, ..., nk with color k, where
(n1 + n2 + ... + nk) = N.
	By application of Polya enumeration formula, the number of
colorings is the coefficient of x1↑n1 * x2↑n2 * ... * xk↑nk in the
cycle index of G.  (The cycle index of a group is a polynomial expressed
as a sum of products of sums of powers of the xi's.)  The existing 
program will work, given the cycle index in a suitable representation.
The project will consist of adding a preprocessor which will compute 
the cycle index given a group in permutation list form, improving
the algorithm by eliminating expansion of terms which will not 
contribute to the final sum, and possibly writing/rewriting the
algorithm so that it counts the number of double cosets (in Sn, given
two groups G and H; the above program is a special case of this).
(As an alternative to the third part, you might expand it to work
on some other application of general Polya enumeration.)
Larry will have further details shortly.

			***************

	A possible portion of all projects would be the translation
of the program from UCI/AI LISP to INTERLISP.

	Projects will be due Thursday, May 30.